#include <cstdio>
#include <algorithm>
using namespace std;
int fun(int a,int b,int n){
    if(a==b){
        return n;
    }
    else{
        return fun(max(a-b,b),min(a-b,b),n)+1;
    }
}
int main(void){
    int t;
    scanf("%d",&t);
    int n,m;
    while(t--){
        scanf("%d%d",&n,&m);
        printf("%d\n",fun(max(n,m),min(n,m),1));
    }
    return 0;
}
